#include <iostream>
#include <vector>
using namespace std;

class Solution {
   public:
	/**
	 *
	 * @param matrix int整型vector<vector<>> the matrix
	 * @return int整型
	 */
	int minPathSum(vector<vector<int> > &matrix) {
		int matrixRowLen = matrix.size();
		if(matrixRowLen == 0) {
			return 0;
		}
		int matrixCowLen = matrix[0].size();
		if(matrixCowLen == 0) {
			return 0;
		}

		vector<vector<int> > dp(matrixRowLen, vector<int>(matrixCowLen, 0));
		dp[0][0] = matrix[0][0];

		for(int i = 1; i < matrixCowLen; i++) {
			dp[0][i] = dp[0][i - 1] + matrix[0][i];
		}
		for(int i = 1; i < matrixRowLen; i++) {
			dp[i][0] = dp[i - 1][0] + matrix[i][0];
		}

		for(int i = 1; i < matrixRowLen; i++) {
			for(int j = 1; j < matrixCowLen; j++) {
				dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
			}
		}

		return dp[matrixRowLen - 1][matrixCowLen - 1];
	}
};
